package A一周刷爆LeetCode.A基础班.F二叉树;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author wei.zhao
 * @description: 求二叉树的最大宽度
 * @date 2022年02月18日 9:48
 */
public class Code04_MaxWidth {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
        head.left.left.left = new Node(8);
        int maxWidth = getMaxWidth(head);
        System.out.println("当前二叉树的最大宽度是：" + maxWidth);
    }

    public static int getMaxWidth(Node head) {
        int max = 0;
        if (head == null) {
            return max;
        }
        LinkedList<Node> list = new LinkedList<>();
        list.push(head);
        //记录每个节点所属的层级
        Map<Node, Integer> map = new HashMap<>();
        map.put(head, 1);
        int curLevel = 0;
        int curMax = 0;
        while (!list.isEmpty()) {
            Node node = list.poll();
            Integer level = map.get(node);
            if (level == curLevel) {
                curMax++;
            } else {
                max = Math.max(curMax, max);
                curLevel = level;
                curMax = 1;
            }
            if (node.left != null) {
                list.add(node.left);
                map.put(node.left, map.get(node) + 1);
            }
            if (node.right != null) {
                list.add(node.right);
                map.put(node.right, map.get(node) + 1);
            }
        }
        return max;
    }

}
